﻿				/*(2024-07-26_vector迭代器失效问题等_作业*/



#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

//// 26. 删除有序数组中的重复项
//// https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
//
//// iterator erase (iterator position);
//// iterator erase (iterator first, iterator last);
//
//class Solution
//{
//public:
//    int removeDuplicates(vector<int>& nums)
//    {
//        int size = nums.size();
//        vector<int>book;
//        auto it1 = nums.begin();
//        auto it2 = nums.begin() + 1;
//        while (it1 != nums.end())
//        {
//            while (it2 != nums.end() && *it1 == *it2)
//                it2++;
//
//            nums.erase(it1 + 1, it2);
//            it1++;
//            it2 = it1 + 1;
//        }
//
//        return nums.size();
//    }
//};


//// JZ39 数组中出现次数超过一半的数字
//// https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//
//// 法一：haxi，空间复杂度、时间复杂度不符合
//// 法二：排序，中间的就是答案，时间复杂度不符合
//// 法三：两个数不相同，就删除这两个数，最后剩下的一定是答案，注意！！！！！！！！！！！！erase是左闭右开的！！！！！！！！！
///*
//候选法（最优解）
//加入数组中存在众数，那么众数一定大于数组的长度的一半。
//思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。
//*/
//
//class Solution
//{
//public:
//    int MoreThanHalfNum_Solution2(vector<int>& numbers)
//    {
//        sort(numbers.begin(), numbers.end());
//        cout << numbers[numbers.size() / 2];
//        return numbers[numbers.size() / 2];
//    }
//
//    int MoreThanHalfNum_Solution(vector<int>& numbers)
//    {
//        for (int i = 0; i < numbers.size(); i++)
//        {
//            cout << numbers[i] << " ";
//        }
//        cout << endl;
//
//        for (int i = 0; i < numbers.size() - 1;)
//        {
//            if (numbers[i] != numbers[i + 1])
//            {
//                numbers.erase(numbers.begin() + i, numbers.begin() + i + 1 + 1);
//                if (i != 0)
//                    i--;
//            }
//            else
//                i++;
//        }
//
//        for (int i = 0; i < numbers.size(); i++)
//        {
//            cout << numbers[i] << " ";
//        }
//        cout << endl;
//        cout << endl;
//        cout << numbers[0] << endl;
//        return numbers[0];
//    }
//};
//
//void solve1()
//{
//    vector<int>nums = { 2, 6, 6, 6, 18, 18, 6, 3, 6, 6, 1 };
//    Solution a;
//    a.MoreThanHalfNum_Solution(nums);
//}
//
//void solve2()
//{// 对拍
//    srand((unsigned int)time(NULL));
//    Solution a;
//    vector<int>nums;
//    for (int i = 0; i < 5; i++)
//        nums.push_back((rand() + i) % 20);
//    for (int i = 0; i < 6; i++)
//        nums.insert(nums.begin() + (rand() + i) % (nums.size()), 6);
//
//    a.MoreThanHalfNum_Solution(nums);
//    a.MoreThanHalfNum_Solution2(nums);
//}
//
//int main()
//{
//    // 
//    // solve1();
//    // solve2();
//    std::vector<int> vec = { 1, 2, 3, 4, 5 };
//    vec.erase(vec.begin() + 1, vec.begin() + 4); // 从索引 1 开始删除，直到索引 4 之前
//    for (auto e : vec)
//        cout << e << ' ';
//    return 0;
//}


//// 下面程序的输出结果正确的是(    )
//
//int main()
//{
//    int ar[] = { 1,2,3,4,0,5,6,7,8,9 };
//    int n = sizeof(ar) / sizeof(int);
//    vector<int> v(ar, ar + n);
//    vector<int>::iterator it = v.begin();
//
//    while (it != v.end())
//    {
//        if (*it != 0)
//            cout << *it;
//        else
//            it = v.erase(it);// 12346789
//            v.erase(it);// 崩溃
//        it++;
//    }
//
//    return 0;
//}